package demo1;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //删除并获得点数
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int key = nums[n-1];
        int[] arr = new int[key+1];key = 0;
        for (int i = 0; i < n; i++) {
            if(nums[i]==key){
                arr[key] += key;
            }else {
                key = nums[i];
                arr[key] = arr[key]+key;
            }
        }
        n = arr.length;
        if(n==0) return 0;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = arr[0];
        for (int i = 1; i < n; i++) {
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(g[n-1],f[n-1]);
    }

    public static void main1(String[] args) {
        int[] nums = {1,2,3,1};
        int[] tmp = Arrays.copyOfRange(nums,2,3);
        System.out.println(Arrays.toString(tmp));
    }

    //打家劫舍 1
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==0) return 0;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(g[n-1],f[n-1]);
    }

    //打家劫舍 2
    public int rob2(int[] nums) {
        int n = nums.length;
        if (n <= 3) {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                max = Math.max(nums[i],max);
            }
            return max;
        }
        int x = rob(Arrays.copyOfRange(nums,1,n));
        int y = rob(Arrays.copyOfRange(nums,2,n-1));
        return Math.max(x,y);
    }

    //按摩师
    public int massage(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+2];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n+1; i++) {
            if(i==2) dp[i] = nums[i-2];
            else
                dp[i] = Math.max(dp[i-2],dp[i-3]) + nums[i-2];
        }
        return Math.max(dp[n],dp[n+1]);
    }

    //地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length;
        int m = dungeon[0].length;
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i < m+1; i++) {
            dp[n][i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n+1; i++) {
            dp[i][m] = Integer.MAX_VALUE;
        }
        dp[n][m-1] = 1;
        for (int i = n-1; i >= 0; i--) {
            for (int j = m-1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                if(dp[i][j]<=0) dp[i][j] = 1;
            }
        }
        return dp[0][0];
    }
}















